#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define EMPTY 0
#define NOT_EMPTY 1
typedef int Status;
typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
}Node;
typedef Node *LinkList;

void operationSystem(LinkList *L);
Status initLinkList(LinkList *L);
Status seeThroughLinkList(LinkList L);
Status listEmpty(LinkList L);
Status destroyLinkList(LinkList *L);
Status getElem(LinkList L,ElemType *data);
Status addElem(LinkList *L,ElemType add);
Status insertElem(LinkList *L,ElemType insert);
Status deleteElem(LinkList *L);
Status locateElem(LinkList L);

int main() {
    setbuf(stdout,NULL);
    printf("Welcome to LinkListDemo!\n");
    printf("----------------------------------------------------------\n");
    LinkList L;
    initLinkList(&L);
    seeThroughLinkList(L);
    operationSystem(&L);
    return 0;
}
//操作面板，用于处理链表的各种操作
void operationSystem(LinkList *L) {
    int operation = 0;
    int data;
    printf("----------------------------------------------------------\n");
    printf("Please select what you want to do to the linkList:\n");
    printf("1 :See through the linkList if you have initialized one\n");
    printf("2 :get the data from the position you want\n");
    printf("3 :add elem to the linkList\n");
    printf("4 :insert data to the position you want\n");
    printf("5 :delete the data of the position you want\n");
    printf("6 :locate a elem in the linkList\n");
    printf("-1:Destroy the linkList\n");
    printf("----------------------------------------------------------\n");
    scanf("%d",&operation);
    switch (operation) {
        case 1:
            seeThroughLinkList(*L);
            operationSystem(L);
            break;
        case 2:
            getElem(*L,&data);
            operationSystem(L);
            break;
        case 3:
            addElem(L,101);
            operationSystem(L);
            break;
        case 4:
            insertElem(L,-100);
            operationSystem(L);
            break;
        case 5:
            deleteElem(L);
            operationSystem(L);
            break;
        case 6:
            locateElem(*L);
            operationSystem(L);
            break;
        case -1:
            destroyLinkList(L);
            printf("LinkList has been destroyed,program will exit soon.\n");
            break;
        default:
            break;
    }
}
//初始化链表,随机插入1-100的数据
Status initLinkList(LinkList *L) {
    printf("Please initialize the LinkList,you may enter the length of it(default is 100,and no longer than 100):\n");
    int length = MAXSIZE;
    scanf("%d",&length);
    if (length > 100) length = 100;
    LinkList p;
    srand(time(0));
    *L = (LinkList) malloc(sizeof(Node));
    (*L) -> next = NULL;
    for (int j = 0; j < length; ++j) {
        p = (LinkList) malloc(sizeof(Node));
        p -> data = rand() % 100 + 1;
        p -> next = (*L) -> next;
        (*L) -> next = p;//将元素插入表头（始终让新元素节点在第一的位置）
    }
    
//     //另：按照先来后到的顺序代码实现如下：
//    LinkList p,r;
//    srand(time(0));
//    *L = (LinkList) malloc(sizeof(Node));
//    r = *L;
//    for (int j = 0; j < length; ++j) {
//        p = (Node *) malloc(sizeof(Node));
//        p -> data = rand() % 100 + 1;
//        r -> next = p;
//        r = p;
//    }
//    r -> next = NULL;
    (*L) -> data = length;//头节点用于存放链表的长度
    printf(" LinkList Initialize successfully!\n");
    return OK;
}
//从头节点开始遍历链表
Status seeThroughLinkList(LinkList L) {
    printf("now the linkList is below:\n");
    LinkList p;
    p = L->next;
    while(p) {
        printf("%d ",p->data);
        p = p -> next;
    }
    printf("\n");
    return OK;
}
//判断链表是否为空
Status listEmpty(LinkList L) {
    if (L -> next == NULL) return EMPTY;
    else return NOT_EMPTY;
}
//销毁链表
Status destroyLinkList(LinkList *L) {
    printf("Warning:You are going to destroy the linkList you have created!\nAre you sure to continue?\n");
    printf("1:YES,0:NO\n");
    int judge = 0;
    scanf("%d",&judge);
    if (judge == 0) {
        printf("destroy canceled\n");
        return FALSE;
    }
    LinkList p,q;
     p = (*L) -> next;
    while (p) {
         q = p -> next;
         free(p);
         p = q;
    }
    (*L) -> next = NULL;
    printf("Destroy successfully!\n");
    return OK;
}
//获取链表第i个位置节点的数据
Status getElem (LinkList L,ElemType *data) {
    int position;
    printf("Please enter the position:\n");
    scanf("%d",&position);
    if (position <= 0 || position > L -> data) {
        printf("the position you have entered is valid,function will exit soon.\n");
        return ERROR;
    }
    int j = 1;
    LinkList p;
    p = L -> next;
    while (p && j < position) {
        p = p -> next;
        j++;
    }
//    if (!p || j > position) return ERROR;
    *data = p -> data;
    printf("The data at position %d is %d\n",position,*data);
    position = 0;
    return OK;
}
//在链表末尾添加元素,为简化，将加入的元素统一设置为101
Status addElem(LinkList *L,ElemType add) {
    int i = 1;
    LinkList p,s;
    s = malloc(sizeof(Node));
    s -> data = add;
    s -> next = NULL;
    p = (*L) -> next;
    while (p && i < (*L) -> data) {
        p = p -> next;
        i++;
    }
    p -> next = s;
    (*L) -> data++;
    seeThroughLinkList((*L));
    return OK;
}
//在链表的第position个位置插入元素insert,为了简化，将插入元素统一设置为-100
Status insertElem(LinkList *L,ElemType insert) {
    printf("Please enter the position you want to insert:\n");
    int position,i;
    scanf("%d",&position);
    i = 1;
    if (position <= 0 || position > (*L) -> data) {
        printf("the position you have entered is valid,function will exit soon.\n");
        return ERROR;
    }
    LinkList s,p;
    s = (LinkList) malloc(sizeof(Node));
    p = (*L);
    s -> data = insert;
    s -> next = NULL;
    while (p && i < position) {
        p = p -> next;
        i++;
    }
    s -> next = p -> next;
    p -> next = s;
    (*L)->data++;
    seeThroughLinkList(*L);
    return OK;
}
//删除链表的第position个元素
Status deleteElem(LinkList *L) {
    printf("Please enter the position:\n");
    int position,i;
    LinkList p,s;
    p = (*L);
    i = 1;
    scanf("%d",&position);
    if (position <= 0 || position > (*L) -> data) {
        printf("the position you have entered is valid,function will exit soon.\n");
        return ERROR;
    }
    while (p && i < position) {
        p = p -> next;
        i++;
    }
    s = p->next;
    p -> next = s-> next;
    free(s);
    (*L) -> data--;
    seeThroughLinkList((*L));
    return OK;
}
//查找定位元素,如果该元素存在，则返回&打印他的位置，否则返回ERROR
Status locateElem(LinkList L) {
    printf("Please enter the elem you want to locate:\n");
    ElemType locate;
    scanf("%d",&locate);
    LinkList p = L->next;
    int position = 1;
    while (p) {
        if (locate == p -> data) {
            seeThroughLinkList(L);
            printf("the elem %d is located at position %d\n",locate,position);
            return position;
        }
        else {
            p = p -> next;
            position++;
        }
        if(!p) {
            seeThroughLinkList(L);
            printf("There is no %d in the LinkList\n",locate);
            return ERROR;
        }
    }
}

